% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.3 for LaTeX2e
%
\documentclass{llncs}
%
\usepackage{makeidx}  % allows for indexgeneration
\usepackage{amsmath}
\usepackage{amsfonts,amssymb}
\usepackage[thinlines,thiklines]{easybmat}
\usepackage{multirow}
\usepackage{algorithmic}
\usepackage{algorithm}
\usepackage{amsthm}


\bibliographystyle{amsplain}

\newtheorem*{theorem*}{Theorem}

\newcommand{\N}{\mathbb{N}} % les entiers naturels
\newcommand{\Z}{\mathbb{Z}} % les entiers relatifs
\newcommand{\Q}{\mathbb{Q}} % les rationnels
\newcommand{\C}{\mathbb{C}} % les complexes
\newcommand{\R}{\mathbb{R}} % les reels
\newcommand{\F}{\mathbb{F}} % un corps fini
\newcommand{\p}{\mathfrak{p}} % un p gothik
\newcommand{\OK}{\mathcal{O}_K}
\newcommand{\Nm}{\mathcal{N}}
\newcommand{\ag}{\mathfrak{a}}
\newcommand{\bg}{\mathfrak{b}}
\newcommand{\cg}{\mathfrak{c}}
\newcommand{\dg}{\mathfrak{d}}
\newcommand{\g}{\mathfrak{g}}
\newcommand{\add}{\alpha_{d,\Delta , \gamma}}
\newcommand{\bdd}{\beta_{d,\Delta , \gamma}}
\newcommand\Ec{\mathcal{E}}
\newcommand\Ac{\mathcal{A}}
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}


%
\begin{document}


\mainmatter              % start of the contributions
%
\title{An algorithm for list decoding number field codes}
%
\titlerunning{List decoding number field codes}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{Jean-Fran\c{c}ois Biasse\inst{1} \and Guillaume Quintin \inst{2}}
%
\authorrunning{J-F Biasse and G. Quintin}   % abbreviated author list (for running head)
%
%%%% list of authors for the TOC (use if author list has to be modified)
\tocauthor{Jean-Fran\c{c}ois Biasse  Guillaume Quintin}
%
\institute{
Department of Computer Science, University of Calgary \\
2500 University Drive NW, Calgary, Alberta, Canada T2N 1N4\\
\email{biasse@lix.polytechnique.fr}
\and
 \'{E}cole Polytechnique, 91128 Palaiseau, France\\
\email{quintin@lix.polytechnique.fr}}

\maketitle              % typeset the title of the contribution

\begin{abstract}
We present an algorithm for list decoding codewords of algebraic number field codes in polynomial time. 
This is the first explicit procedure for decoding number field codes whose construction were previously described by 
Lenstra~\cite{lenstra_nb_fld} and Guruswami~\cite{guruswami_nb_fld}. We rely on an equivalent of the LLL 
reduction algorithm for $\OK$-modules due to Fieker and Stehl\'{e}~\cite{stehle_fieker_LLL} and on algorithms due
to Cohen~\cite{cohen2} for computing the Hermite normal form of matrices representing modules over Dedekind domains.
\end{abstract}


\section{Introduction}

Algorithms for list decoding Reed-Solomon codes, and their generalization the algebraic-geometric codes 
are now well understood. The codewords consist of sets of functions whose evaluation at a certain number of points 
are sent, thus allowing the receiver to retrieve them provided that the number of errors is manageable. Some algebraic-geometric 
codes beat the Gilbert-Varshamov bound for alphabet sizes $q > 49$ (see~\cite{garcia_stich,Zink}), and possess a nice algebraic structure which enables to decode even in the presence of a large number of errors~\cite{guruswami_sudan_reed_sol,wasserman}.

The idea behind behind algebraic-geometric codes can be adapted to define algebraic codes whose messages are encoded 
as a list of residues redundant enough to allow errors during the transmission. The Chinese Remainder codes (CRT codes) have been fairly studied by the community~\cite{guruswami_sudan_soft_CRT,Mandelbaum}. The encoded messages are residues modulo $N:=p_1,\cdots,p_n$ of numbers $m\leq K:= p_1\cdots p_k$ where $p_1 < p_2 < \cdots < p_n$ are prime numbers. They are encoded by using 
\[   \left. \begin{array}{ccc}
         \Z & \longrightarrow  & \Z/p_1\times \cdots \times \Z/p_n \\
        m & \longmapsto & (m\bmod p_1,\cdots ,m \bmod p_n). \end{array} \right. \] 
Decoding algorithms for CRT codes were significantly improved to reach the same level of tolerance to errors as those 
for Reed-Solomon codes~\cite{Boneh,sudan,guruswami_sudan_soft_CRT}. As algebraic-geometric codes are a generalization of Reed-Solomon codes, the idea arose that we could generalize the results for CRT codes to redundant residue codes based on number fields. Indeed, we can easily define an analogue of the CRT codes where a number field $K$ plays the role of $\Q$ and its ring of integers $\OK$ plays the role of $\Z$. Then, for prime ideals $\p_1,\cdots,\p_n$ such that $\Nm(\p_1) < \cdots < \Nm(\p_n)$, a message $m\in\OK$ can be encoded by using
\[   \left. \begin{array}{cccc}
      &   \OK & \longrightarrow  & \OK/\p_1\times \cdots \times \OK/\p_n \\
    c:&    m & \longmapsto & (m\bmod \p_1,\cdots ,m \bmod \p_n). \end{array} \right. \] 
The construction of good codes on number fields have been independantly studied by Lenstra~\cite{lenstra_nb_fld} and Guruswami~\cite{guruswami_nb_fld}. They provided indications on how to chose number fields having good properties for the underlying codes, but they did not describe any decoding algorithm.

\noindent\textbf{Contribution: }The main contribution of this paper is to provide the first algorithm for decoding number field codes. We adapt an algorithm of Guruswami~\cite[Chap. 7]{guruswami_phd} for CRT codes, and present original contributions to methods for manipulating modules over the ring of integers of a number field (see Section~\ref{sec:computation}). Throughout the article, we denote by $K$ a number field of degree $d$, of discriminant $\Delta$ and of ring of integers $\OK$. The prime ideals $(\p_i)_{i\leq n}$ satisfy $\Nm(\p_1)<\Nm(\p_2)<\cdots<\Nm(\p_n)$, and we define $N:=\prod_{i\leq n}\Nm(\p_i)$ and $B := \prod_{i\leq k}\Nm(\p_i)$ for integers $k,n$ such that $0< k  < n$. Before describing our algorithm in more details in the following sections, let us state the main result of the paper.

\begin{theorem*}
Let $\varepsilon > 0$, and a message $m\in\OK$ satisfying $\| m \| \leq B$, then there is an algorithm that returns all the messages $m'\in\OK$ such that $\| m' \|\leq B$ and that $c(m)$ and $c(m')$ have mutual agreement $t$ satisfying
$$t\geq \sqrt{k(n + \varepsilon)}.$$
This algorithm is polynomial in $d$ , $\log(N)$, $1/\varepsilon$ and $\log|\Delta|$.
\end{theorem*}

\section{Previous work}

Even though little has been done on decoding algorithms for number field codes, their construction is not recent. Indeed, they were described in the 1980's by Lenstra~\cite{lenstra_nb_fld}, and in 2003, Guruswami~\cite{guruswami_nb_fld} introduced classes of number field codes that correspond to the description we gave in the introduction. The main difference between the two approaches is the fact that Lenstra used the residue of the message at both Archimedian and non-Archimedian places whereas the approach of Guruswami (that we followed here) consists of restricting ourselves to Archimedian places. In fact, the approach of Lenstra allows to prove the existence of good asymptotic codes more easily, but it is then harder to pursue the analogy with Reed-Solomon and CRT codes. Nevertheless, Guruswami~\cite{guruswami_nb_fld} exhibited a code family $\{\mathcal{C}_i\}$ of increasing block length $n_i\rightarrow\infty$ such that 
$$\lim\inf\frac{k_i}{n_i} > 0 \ \ \text{and}\ \ \lim\inf\frac{d_i}{n_i} > 0,$$
where $k_i$ denotes the dimension of $\mathcal{C}_i$ and $d_i$ denotes its minimum distance.

In his thesis, Guruswami~\cite[Chap. 7]{guruswami_phd} described a more general framework embracing both algebraic-geometric codes and CRT codes. The messages lie in a ring $R$, and they are encoded via a $n$-uplet of residues modulo coprime ideals $I_1,\cdots, I_n$ of $R$ by using the function
\[   \left. \begin{array}{cccc}
      &   R & \longrightarrow  & R/I_1\times \cdots \times R/I_n \\
    c:&    m & \longmapsto & (m\bmod I_1,\cdots ,m \bmod I_n). \end{array} \right. \]
Then, the messages with sufficient agreement are recovered as roots of a polynomial in $R[y]$. In~\cite{guruswami_phd}, this general approach is applied to CRT codes, as well as to Reed-Solomon codes and algebraic-geometric codes. Finding a suitable polynomial of degree $l$ for decoding boils down to finding short elements in 
a sub $R$-module of $R^{l+1}$. This is achieved in~\cite[Chap. 7]{guruswami_phd} for CRT codes by the means of the LLL algorithm~\cite{LLL}. In this paper, we use an equivalent of this algorithm on $\OK$-modules of $K^{l+1}$ described by Fieker and Stehl\'{e}~\cite{stehle_fieker_LLL}, and we provide a proper analysis of the construction of the module containing our decoding polynomial, thus allowing to follow the approach of the general framework~\cite[Chap. 7]{guruswami_phd}. We use the same notations as in~\cite[Chap. 7]{guruswami_phd} as much as possible, however, the proof of many results need to be adjusted to our context, although the general strategy remains unchanged. As we see in Section~\ref{sec:computation}, the major technical difference is that we need to manipulate $\OK$-modules defined by their pseudo-basis.

Note that Cohn and Heninger~\cite{Coppersmith} recently gave an ideal form of Coppersmith's theorem that can be applied to enhance list decoding of Reed-Solomon and Algebraic-geometric codes. They used a weak version of the result of Fieker and Stehl\'{e}~\cite{stehle_fieker_LLL} to give a variant of this theorem for number fields. They discussed its applications to the shortest vector problem in integral lattices in the context of lattice-based cryptography, but they did not consider the possibility to list decode number field codes.

\section{Generalities on number fields}

Let $K$ be a number field of degree $d$. It has $r_1\leq d$ real embeddings $(\theta_i)_{i\leq r_1}$ and $2r_2$ complex embeddings $(\theta_i)_{r_1 < i \leq 2r_2}$ (coming as $r_2$ pairs of conjugates). The field $K$ is isomorphic to $\OK\otimes\Q$ where $\OK$ denotes the ring of integers of $K$. We can embed $K$ in 
$$K_\R := K\otimes \R \simeq \R^{r_1}\times \C^{r_2}, $$ 
and extend the $\theta_i$'s to $K_\R$. Let $T_2$ be the Hermitian form on $K_\R$ defined by 
$$T_2(x,x') := \sum_i \theta_i(x)\overline{\theta_i}(x'),$$
and let $\| x\| := \sqrt{T_2(x,x)}$ be the corresponding $L_2$-norm. Let $(\alpha_i)_{i\leq d}$ such that $\OK = \oplus_i \Z\alpha_i$, then the discriminant of $K$ is given by $\Delta = \det^2(T_2(\alpha_i,\alpha_j))$. The norm of an element $x\in K$ is defined by $\Nm(x) = \prod_i|\theta_i(x)|$.

We encode our messages with prime ideals of $\OK$. However, for decoding, we need a more general notion of ideal, namely the fractional ideals of $\OK$. They can be defined as finitely generated $\OK$-modules of $K$. When a fractional ideal is contained in $\OK$, we refer to it as an integral ideal, which is in fact an ideal of $\OK$. For every fractional ideal $I$ of $\OK$, there exists $r\in\Z$ such that $rI$ is integral. The sum and product of two fractional ideals of $\OK$ is given by 
\begin{align*}
IJ &= \{ i_1j_1 + \cdots + i_lj_l\mid l\in \N, i_1,\cdots i_l\in I, j_1,\cdots j_l\in J\}\\
I + J &= \{ i + j\mid i\in I , j\in J\}.
\end{align*}
The fractional ideals of $\OK$ are invertible, that is for every fractional ideal $I$, there exists $I^{-1}:= \{ x\in K\mid xI\subseteq \OK\}$ such that $II^{-1} = \OK$. The set of fractional ideals is equipped with a norm function defined by $\Nm(I) = \det(I)/\det(\OK)$. The norm of ideals is multiplicative, and in the case of an integral ideal, we have $\Nm(I) = |\OK / I|$. Also note that the norm of $x\in K$ is precisely the norm of the principal ideal $(x) = x\OK$. Algorithms for ideal arithmetic in polynomial time in the bit size of $\Delta$ are extensively described in~\cite{cohen}.

In the following, we will study finitely generated sub $\OK$-module of $\OK[y]$. Let $M\subseteq K^l$ be a finitely generated $\OK$-module. As in~\cite[Chap. 1]{cohen2}, we say that $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$, where $a_i\in K$ and $\mathfrak{a}_i$ is a fractional ideal, is a pseudo-basis for $M$ if
$$M = \mathfrak{a}_1a_1\oplus \cdots \oplus \mathfrak{a}_na_n.$$
Note that a pseudo-basis is not unique, and the main result of~\cite{stehle_fieker_LLL} is precisely to compute a pseudo-basis of short elements. If the sum is not direct, we call $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$ a pseudo-generating set for $M$. Once a pseudo-generating set $[(a_i),(\mathfrak{a}_i)]_{i\leq n}$ for $M$ is known, we can associate a pseudo-matrix $A = (A,I)$ to $M$, where $A\in K^{n\times l}$ and $I = (\ag_i)_{i\leq n}$ is a list of $n$ fractional ideals such that 
$$M = \ag_1 A_1 + \cdots +\ag_n A_n,$$
where $A_i\in K^l$ is the $i$-th row of $A$. We can construct a pseudo-basis from a pseudo-generating set by using the Hermite normal form (HNF) over Dedekind domains (see ~\cite[Th. 1.4.6]{cohen2}). Assume $A$ is of rank $l$ (in particular  $n\geq l$), then there exists a $n\times n$ matrix $U = (u_{i,j})$ and $n$ non-zero ideals $\bg_1, \cdots , \bg_n$ satisfying 
\begin{enumerate}
 \item $\forall i,j, u_{i,j}\in \bg_i^{-1}\ag_j$.
 \item $\ag = \det(U)\bg$ for $\ag = \prod_i\ag_i$ and $\bg = \prod_i \bg_i$.
 \item The matrix $UA$ is of the form\\
\[ UA = \left( 
   \begin{BMAT}(@)[0.5pt,2cm,2cm]{c}{c.c}
   \begin{BMAT}(e)[1pt,1cm,1cm]{cccc}{cccc}
1      & 0      & \hdots & 0      \\
\vdots & 1      & \ddots & \vdots \\
\vdots & \vdots & \ddots & 0      \\
*      & *      & \hdots & 1\\
  \end{BMAT} \\
\begin{BMAT}[0.5pt,1cm,1cm]{c}{c} 
        (0)
\end{BMAT}
\end{BMAT}
   \right).
\]

 \item $M = \bg_{1}\omega_1\oplus \cdots \oplus \bg_{l}\omega_l$ where $\omega_1,\cdots \omega_l$ are the first $l$ rows of $UA$.
\end{enumerate}

In general, the algorithm of~\cite{cohen2} for computing the HNF of a pseudo-matrix takes exponential time, but as in the integer case, there exists a modular one which is polynomial in the dimensions of $A$, the degree of $K$, and the bit size of the modulo. Note that in the case of a pseudo matrix representing an $\OK$-module $M$, the modulo an integral multiple of the determinantal ideal $\g(M)$, which is generated by all the ideals of the form 
$$\det_{i_1,\cdots,i_l}(A)\cdot \ag_{i_1}\cdots\ag_{i_l},$$
where $\det_{i_1,\cdots,i_l}(A)$ is the determinant of the $l\times l$ minor consisting of the rows of indices $i_1,\cdots,i_l$. The determinantal ideal is a rather involved structure, except in the case $l = n$.

\section{Johnson-type bound for number fields codes}

\input{johnson.tex}

\section{General description of the algorithm}

In this section, we give a high-level description of our decoding algorithm. We follow the approach of the general framework described in~\cite{guruswami_phd}, making the arrangements required in our context. Our code is the set of $m\in\OK$ such that $\|m\|\leq B$ where $B = \prod_{i\leq k}\Nm(\p_i)$. We also define $N:=\prod_{i\leq n}\Nm(\p_i)$. A codeword $m$ is encoded via 
\[   \left. \begin{array}{ccc}
         \OK & \longrightarrow  & \OK/\p_1\times \cdots \times \OK/\p_n \\
       m & \longmapsto & (m\bmod \p_1,\cdots ,m \bmod \p_n). \end{array} \right. \] 
Let $z_1,\cdots,z_n$ be non-negative real numbers, and let $Z$ be a parameter. In this section, as well as in Section~\ref{sec:existence} and~\ref{sec:computation}, we assume that the $z_i$ are integers. We assume that we received a vector $r_1,\cdots,r_n\in\prod_i\OK/\p_i$. We wish to retrieve all the codewords $m$ such that $\sum_i a_iz_i > Z$ where $a_i=1$ if $m\bmod \p_i = r_i$ and 0 otherwise (we say that $m$ and $(r_i)_{i\leq n}$ have weighted agreement $Z$).

We find the codewords $m$ with desired weighted agreement by computing roots of a polynomial $c\in\OK[y]$ that satisfies 
\begin{equation}\label{eq:cond_norm}
\|m\|\leq B \Longrightarrow \|c(m)\| < F,
\end{equation} 
for an appropriate bound $F$. A polynomial $c$ satisfying~\eqref{eq:cond_norm} is chosen in the ideal $\prod_{i\leq n}J_i^{z_i}\subseteq\OK[y]$ where
$$J_i = \{ a(y)(y-r_i) + p\cdot b(y)\mid a,b\in\OK[y]\ \text{and}\ p\in\p_i\}.$$
With such a choice of a polynomial, we necessarily have $c(m)\in\prod_i \p_i^{z_ia_i}$, where $a_i = 1$ if $c(m)\bmod \p_i = r_i$, $0$ otherwise. In particular, if $c(m)\neq 0$ this means that $\Nm(c(m)) \geq \prod_i\Nm(\p_i)^{z_ia_i}$. In addition, we know from the arithmetic-geometric inequality that $\|c(m)\| \geq \sqrt{d}\Nm(c(m))^{1/d}$. We thus know that if the weighted agreement satisfies 
\begin{equation}\label{eq:cond_weight}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) > -\frac{d}{2}\log(d) + d\log(F),
\end{equation}
which in turns implies $\sqrt{d}\left(\prod_i\Nm(\p_i)^{z_ia_i}\right)^{1/d} > F$, then $c(m)$ has to be zero, since otherwise it would contradict~\eqref{eq:cond_norm}.

\begin{algorithm}[H]
\caption{Decoding algorithm}
\begin{algorithmic}[1]\label{alg:decoding}
\REQUIRE $\OK$, $z_1,\cdots,z_n$, $B$, $Z$, $r_1,\cdots,r_n\in\prod_i\OK/\p_i$.
\ENSURE All $m$ such that $\sum_i a_iz_i > Z$.
\STATE Compute $l$ and $F$.
\STATE Find $c\in\prod_{i\leq n}J_i^{z_i}\subseteq\OK[y]$ of degree at most $l$ such that $\|m\|\leq B \Longrightarrow \|c(m)\| < F$.
\STATE Find all roots of $c$ and report those roots $\xi$ such that $\|\xi\|\leq B$ and $\sum_i a_iz_i > Z$.
\end{algorithmic}
\end{algorithm}


\section{Existence of the decoding polynomial}\label{sec:existence}

In this section, we prove the existence of a polynomial $c\in\OK[y]$ and a constant $F>0$ such that for all $\|m\|\leq B$, $m\in\OK$, we have $\|c(m)\|\leq F$. This proof is not constructive. The actual computation of this polynomial will be described in Section~\ref{sec:computation}. We first need to estimate the number of elements of $\OK$ bounded by a given size. 

\begin{lemma}\label{lem:Minkowski}
Let $F'>0$ and $0<\gamma < 1$, then the number of $x\in\OK$ such that $\|x\|\leq F'$ is at least
$$\left\lfloor \frac{\pi^{d/2}F'^d}{2^{r_1+r_2-1+\gamma}\sqrt{|\Delta|}\Gamma(d/2)}\right\rfloor.$$
\end{lemma}

\begin{proof}
As in~\cite[Chap. 5]{neukirch}, we use the standard results of Minkowski theory for our purposes. More precisely, there is an isomorphism
$$f:K_\R\longrightarrow \R^{r_1 + 2r_2}$$
and a scalar product $(x,y) := \sum_{i\leq r_1}x_iy_i + \sum_{r_1<i\leq r_2}2x_iy_i$ on $\R^{r_1+2r_2}$ transfering the canonical measure from $K_\R$ to $\R^{r_1+2r_2}$. Let $\lambda = f(\OK)$, $X := \{ x\in K_\R\mid \|x\|\leq F'\}$, and $m\in\N$. We know from Minkowski's lattice point theorem that if
$$\operatorname{Vol}(X) > m2^d\det(\lambda),$$
then $\#(f(x)\cap\lambda) \geq m$. As $\operatorname{Vol}(X) = 2^{r_2}\left(2\pi^{d/2}F'^d/\Gamma(d/2)\right)$ and $\det(\lambda) = \sqrt{|\Delta|}$, we have the desired result.
\end{proof}

Then, we must derive from Lemma~\ref{lem:Minkowski} an analogue of~\cite[Lemma 7.6]{guruswami_phd} in our context. This lemma allows us to estimate the number of polynomials of degree $l$ satisfying~\eqref{eq:cond_norm}. To simplify the expressions, we use the following notation in the rest of the paper
$$\add := \frac{\pi^{d/2}}{2^{r_1 + r2-1 + \gamma}\sqrt{|\Delta|}\Gamma(d/2)}.$$

\begin{lemma}\label{lem:nb_pol}
For positive integers $B,F'$, the number of polynomial $c\in\OK[y]$ of degree at most $l$ satisfying~\eqref{eq:cond_norm} is at least
$$\left( \add \left( \frac{F'}{(l+1)B^{l/2}}\right)^d\right)^{l+1}.$$ 
\end{lemma}

\begin{proof}
Let $c(y) = c_0 + c_1y + \cdots + c_ly^l$. We want the $c_i$'s to satisfy $\|c_im^i\|< F'/(l+1)$ whenever $\|m\|\leq B$. This is the case when $\|c_i\| < F'/(B^i(l+1))$. By Lemma~\ref{lem:Minkowski}, there are at least $\add\left(F'/((l+1)B^i)\right)^d$ possibilities for $c_i$. Therefore, the number of polynomial $c$ satisfying~\eqref{eq:cond_norm} is at least 
$$(\add)^{l+1}\left(\left(\frac{F'}{l+1}\right)^{l+1}\prod^l_{i = 0}B^{-i}\right)^d,$$
which finishes the proof. 
\end{proof}

Now that we know how to estimate the number of $c\in\OK[y]$ or degree at most $l$ satisfying~\eqref{eq:cond_norm}, we need to find a lower bound on $F$ to ensure that we can find such a polynomial in $\prod_iJ_i^{z_i}$. The following lemma is an equivalent of~\cite[Lemma 7.7]{guruswami_phd}.

\begin{lemma}
Let $l,B,F$ be positive integers, there exists $c\in\prod_i J_i^{z_i}$ satisfying~\eqref{eq:cond_norm} provided that
\begin{equation}\label{eq:cond_F}
F > 2(l+1)B^{l/2}\frac{1}{(\add)^{1/d}}\left(\prod_i\Nm(\p_i)^{\binom{z_i+1}{2}}\right)^{\frac{1}{d(l+1)}}.
\end{equation}
\end{lemma} 

\begin{proof}
Let us apply Lemma~\ref{lem:nb_pol} to $F' = F/2$. There are at least 
$$\left( \add \left( \frac{F/2}{(l+1)B^{l/2}}\right)^d\right)^{l+1}$$
polynomial $c\in\OK[y]$ satisfying $\|m\|\leq B\Rightarrow \|c(m)\| < F/2$. In addition, we know from~\cite[Corollary 7.5]{guruswami_phd} that $\prod_i\left|\Nm(\p_i)\right|^{\binom{z_i+1}{2}}\geq \left|\OK[y]/\prod_i J_i^{z_i}\right|$, which implies that if~\eqref{eq:cond_F} is satisfied, then necessarily
$$\left( \add \left( \frac{F/2}{(l+1)B^{l/2}}\right)^d\right)^{l+1} > \left|\OK[y]/\prod_i J_i^{z_i}\right|.$$
This means that there are at least two distinct polynomials $c_1,c_2\in\OK[y]$ of degree at most $l$ such that $(c_1-c_2)\in\prod_i J_i^{z_i}$ and $\|c_1(m)\|,\|c_2(m)\| < F/2$ whenever $\|m\|\leq B$. The choice of $c:=c_1-c_2$ finishes the proof.
\end{proof}

\section{Computation of the decoding polynomial}\label{sec:computation}

Let $l>0$ be an integer to be determined later. To compute $c\in\prod_i J_i^{z_i}$ of degree at most $l$ satisfying~\eqref{eq:cond_norm}, we need to find a short pseudo-basis of the sub $\OK$-module $M$ of $K^{l+1}$ given by
$$c = c_0 + yc_1 + \cdots + y^lc_l \longrightarrow (c_0 , c_1 , \cdots , c_l).$$
We first compute a peudo-generating set for each $J_i^{z_i}$, then we compute a pseudo-basis for their intersection, and we finally call the algorithm of~\cite{stehle_fieker_LLL} to produce a short peudo-basis of $M$ from which we derive $c$. 

An algorithm for computing a pseudo-basis of the intersection of two modules given by their pseudo basis is described by Cohen in~\cite[1.5.2]{cohen2}. Applying this successively for each pseudo-basis of $J_i^{z_i}$ would certainly produce a pseudo-basis of $\prod_i J_i^{z_i}$, but it would be likely to be exponential. We present in the following an algorithm for computing the intersection of $n$ sub $\OK$-modules of $K^{l+1}$ that is polynomial in $n$, $l$ and the bit size of the product of the $n$ determinantal ideals when the modules are included in $\OK^{l+1}$. 

\begin{algorithm}[ht]
\caption{Intersection of $\OK$-modules}
\begin{algorithmic}[1]\label{alg:int_OK_mod}
\REQUIRE $\OK$-modules $M_1,\cdots,M_n$ given by $(A_1,(\ag^{(1)}_i)_{i\leq l+1}),\cdots,(A_n,(\ag^{(n)}_i)_{i\leq l+1})$.
\ENSURE A pseudo matrix $(H , (\cg_i)_{i\leq l+1})$ representing $\cap_i M_i$
\STATE $\g\leftarrow \g(M_1)\cdots\g(M_n)$, $H_1\leftarrow A_1$, $(\cg_i)_{i\leq l+1}\leftarrow (\ag^1_i)_{i\leq l+1}$.
\FOR { $2\leq k\leq n$ }
\STATE Let $B_k$ be the pseudo matrix given by
\[ B_k = \left( 
   \begin{BMAT}(@)[0.5pt,2cm,2cm]{c.c}{c.c}
A_k & 
   \begin{BMAT}(e)[0.5pt,1.5cm,0.5cm]{cc}{c}
 A_k      & (0)      
  \end{BMAT} \\
(0) & H_{k-1} \\
%\begin{BMAT}[0.5pt,1cm,1cm]{c.c}{c} 
%      (0) & H \\
%\end{BMAT}
\end{BMAT}
   \right),
\]
and the ideals $(\mathfrak{d}_i)_{i\leq k(l+1)} := \ag^i_1,\cdots,\ag^i_{l+1},\cg_{1},\cdots,\cg_{(k-1)(l+1)}$.
\STATE Let $(H_k , (\cg_i)_{i\leq k(l+1)}$ be the Hermite normal form of $(B_k , (\mathfrak{d}_i)_{i\leq k(l+1)})$ modulo $\g$ (by using~\cite[Alg. 1.6.1]{cohen2}).
\ENDFOR
\STATE Let $H$ be the upper left $(l+1)\times (l+1)$ minor of $H_n$.
\RETURN $(H , (\cg_i)_{i\leq l+1})$.
\end{algorithmic}
\end{algorithm}

\begin{proposition}
Let $M_1,\cdots , M_n$ be $\OK$-modules of $K^{l+1}$ given by 
$$(A_1,(\ag^{(1)}_i)_{i\leq l+1}),\cdots,(A_n,(\ag^{(n)}_i)_{i\leq l+1}),$$
where the $\ag^j_i$ are integral ideals of $\OK$ and the $A_i$ have integral coefficients, 
then Algorithm~\ref{alg:int_OK_mod} computes a pseudo-basis for $\cap_i M_i$ in polynomial time in $n$, $l$ and in the bit size of $\g := \g(M_1)\cdots\g(M_n)$.
\end{proposition}

\begin{proof}
We notice that $\forall k\leq n,\ \g(H_k)=\prod^k_{i=1}\g(M_i)$ since it is clear that in the square case, the Hemite normal form computation preserves the determinantal ideal. Therefore, since the $\ag^j_i$ are assumed to be integral and since the $A_i$ have integral coefficients, $\g$ is an integral multiple of $\g(H_k)$ for every $k\leq n$. Thus, the use of~\cite[Alg. 1.6.1]{cohen2} modulo $\g$ in Step 4 is valid, and from~\cite[Th. 1]{stehle_fieker_LLL} we know that it is polynomial in $n,l$ and the bit size of $\g$.

We can see by induction that for all $k\leq n$, the pseudo-matrix defined by the upper left $(l+1)\times(l+1)$ minor of $H_k$ and $\cg_1,\cdots,\cg_{l+1}$ represent $\cap_{i\leq k}M_i$. The first iteration over $k$ is a direct application of~\cite[Alg. 1.5.1]{cohen2}. Let $M,N$ are two modules over a Dedekind domain given by $A,(\ag_i)_{i\leq l+1}$ and $B,(\bg_i)_{i\leq l+1}$, and let $C$ be the pseudo-matrix given by
\[ \left( \begin{array}{cc}
A & A  \\
0 & B  \end{array} \right),\]
and $\cg_1,\cdots,\cg_{2(l+1)}$. Then the upper left $(l+1)\times (l+1)$ minor for the HNF of $C$, together with $\cg_1,\cdots,\cg_n$ represent $M\cap N$. Now if we assume our property for some $k < n$, then $B_{k+1}$ has the shape

\[ B_{k+1} = \left( 
   \begin{BMAT}(@)[0.5pt,3cm,3cm]{c.c}{c.c}
   \begin{BMAT}(e)[0.5pt,1cm,1cm]{cc}{cc}
 A_{k+1}      & A_{k+1} \\
 (0)          & H'_1      
  \end{BMAT} 
 & (0) \\
H'_3 & H'_2 \\
%\begin{BMAT}[0.5pt,1cm,1cm]{c.c}{c} 
%      (0) & H \\
%\end{BMAT}
\end{BMAT}
   \right),
\]

where $H'_2\in K^{(k-1)(l+1)\times (k-1)(l+1)}$ is lower-triangular and $\left(H'_1 , (\cg_i)_{i\leq l+1}\right)$ represent $\cap_{i\leq k}M_i$ (by induction). 

The HNF of $B_{k+1}$ is obtained by using~\cite[Alg. 1.6.1]{cohen2}. The treatment of columns $(k+1)(l+1)$ to $2(l+1)+1$ leaves $H'_2$ and $\cg_{(k+1)(l+1)},\cdots ,\cg_{2(l+1)+1}$ unchanged since they are already in HNF. Then the treatment of columns $2(l+1)$ to $1$ consists of computing the HNF of the pseudo-matrix
\[C_{k+1}:=\left( \begin{array}{cc}
A_{k+1} & A_{k+1}  \\
0       & H'_1  \end{array}\right),(\ag^{(k+1)}_1,\cdots,\ag^{(k+1)}_{l+1},\cg_1,\cdots,\cg_{l+1}),
\]
and of reducing the rows of $H'_3$ with these $C_{k+1}$. Let $\left(U C_{k+1} , (\dg_i)_{i\leq 2(l+1)}\right)$ be the HNF of $\left(C_{k+1},I\right)$, where $U\in K^{2(l+1)\times 2(l+1)}$, and $H'_4$ be the matrix defined by
\[ U \left( \begin{array}{cc}
A_{k+1} & A_{k+1}  \\
0       & H'_1  \end{array}\right) = 
\left( \begin{array}{cc}
H'_4      & (0)  \\
(*)       & (*)  \end{array}\right),\]
then by induction, we know that the pseudo-matrix 
$$(H'_4,(\dg_i)_{i\leq l+1})$$
 represents $\cap_{i\leq k+1}M_i$.

%Therefore, if the HNF of 
%\[\left( \begin{array}{cc}
%A_{k+1} & A_{k+1}  \\
%0       & H'_1  \end{array}\right),(\ag^{k+1}_1,\cdots,\ag^{k+1}_{l+1},\cg_1,\cdots,\cg_{l+1})
%\]
%is obtained by the transformation matrix $U\in K^{2(l+1)\times 2(l+1)}$ and the ideals $(\dg_i)_{i\leq 2(l+1)}$, and %if $H'_3$ is defined as
%\[ U \left( \begin{array}{cc}
%A_{k+1} & A_{k+1}  \\
%0       & H'_1  \end{array}\right) = 
%\left( \begin{array}{cc}
%H'_3 & (0)  \\
%(*)       & (*)  \end{array}\right),\]
%then by~\cite[Alg. 1.5.1]{cohen2} we know that $H'_3,(\dg_i)_{i\leq l+1}$ represents $\cap_{i\leq k+1}M_i$. The %operations required to compute the HNF $B_k$ are the same as these required to put its upper left $2(l+1)\times %2(l+1)$ submatrix in HNF. Therefore, the HNF of $B_k %,(\ag^{k+1}_1,\cdots,\ag^{k+1}_{l+1},\cg_1,\cdots,\cg_{k(l+1)})$ is given by 
%\[ \left( \begin{array}{cc}
%U & (0)  \\
%(0)       & I_{k(l+1)}  \end{array}\right)\cdot B_k = 
%\left( \begin{array}{cc}
%H'_3 & (0)  \\
%(*)       & (*)  \end{array}\right), \]
%and the ideals $(\dg_1,\cdots , \dg_{2(l+1)} , \cg_{l+2} , \cdots , \cg_{k(l+1)})$. Thus, the HNF of $B_k$ computed %in Step 4 satisfies our property for $k+1$, which finishes the proof. 
\end{proof}

\noindent\textbf{Remark:} In the previous proof, the HNF of the upper left $2(l+1)\times 2(l+1)$ minor of $B_k$ has to be recovered from the HNF of $B_k$ itself since we need to perform this operation modulo an integral multiple of the determinantal ideal. We know such a multiple for $B_k$, but not for its upper left $2(l+1)\times 2(l+1)$ minor whose determinantal ideal might be fractional.



\begin{algorithm}[ht]
\caption{Computation of the determinantal ideal}
\begin{algorithmic}[1]\label{alg:det_ideal}
\REQUIRE Pseudo-matrix $A,(\ag_i)_{i\leq l+1}$, where $A$ and the $\ag_i$ are integral. Bound $L\geq \max_{i,j,\sigma}|\sigma(A_{i,j})|$. %Complex embeddings $\sigma_i:K\rightarrow\C$ $z_1,\cdots,z_n$, $i\leq d$.
\ENSURE $\g(A,(\ag_i))$.
\STATE $L_p\leftarrow \sqrt{d}L^{l+1}(l+1)^{(l+1)/2}$.
\STATE Let $p\in\N$ be the smallest prime above $L_p$ and $(\p_i,e_i)_{i\leq g}$ such that $(p)=\prod_{i\leq g}\p_i^{e_i}$. 
\FOR {$\p_i\mid(p)$}
\STATE Compute $\det(A)\bmod \p_i$.
\ENDFOR
\STATE Recover $\det(A)\bmod (p)$ via 
\[   \left. \begin{array}{ccc}
    \OK/\p_1^{e_1}\times \cdots \times \OK/\p_g^{e_g}     & \longrightarrow  &   \OK/(p)\\
    (\det(A)\bmod \p_1^{e_1},\cdots ,\det(A) \bmod \p_g^{e_g})   & \longmapsto & \det(A)\bmod (p). \end{array} \right. \] 
\STATE $\g\leftarrow \det(A)\ag_1\cdots\ag_{l+1}$.
\RETURN $\g$.
\end{algorithmic}
\end{algorithm}

Before presenting the overall strategy for computing our decoding polynomial $c$, let us isolate the step consisting of the computation of the determinantal ideal of $J_i^{z_i}$. 
Algorithm~\ref{alg:det_ideal} computes the determinantal ideal in polynomial time in $d$, $l$ and the bit size of $L$. In Step 1 we first compute an upper bound on $|\sigma(\det(A))|$ for the $d$ complex embeddings of $K$ via Hadamard's inequality and then we deduce a bound $L_p$ on $\|\det(A)\|$. If $\alpha_1,\cdots,\alpha_d$ is an integral basis for $\OK$, and $(a_i)_{i\leq d}$ are integers such that $\det(A) = \sum_{i\leq d}a_i\alpha_i$, then necessarily $\max_i|a_i|\leq L_p$. Then, the unique representant of the class of $\det(A)\bmod (p)$ whose integral coefficients have their absolute value bounded by $p$ is $\det(A)$. Note that for the purpose of a practical implementation, one might prefer computing $\det(A)$ modulo several wordsize primes and recover its value via the chinese remaindering theorem rather than finding directly its value modulo a unique prime larger than $L_p$. Let us now present the overall strategy for computing the decoding polynomial.

\begin{algorithm}[ht]
\caption{Computation of the decoding polynomial}
\begin{algorithmic}[1]\label{alg:comp_c}
\REQUIRE $(\p_i,z_i)_{i\leq n}$, $l$, $N$, $B$, $F$ such that $\exists c\in \prod_iJ_i^{z_i}$ of degree at most $l$ satisfying~\eqref{eq:cond_norm} for $F$, and the encoded message $(r_1,\cdots,r_n)\in\prod_i\OK/\p_i$. 
\ENSURE $c\in \prod_iJ_i^{z_i}$ satisfying~\eqref{eq:cond_norm} for $F' = 2^{\frac{dl}{2}}\sqrt{l+1}\left(2^{2 + d\left(6 + 3d\right)} d^3|\Delta|^{2 + \frac{11}{2d}}\right) F$ of degree at most $l$.
\STATE $L\leftarrow 2^{ld^2/2}\binom{2l}{l}N^l|\Delta|^{l/2}$.
\FOR {$i\leq n$}
\STATE $\tilde{z_i}\leftarrow \min(z_i,l)$.
\STATE For $0\leq j\leq \tilde{z_i}$: $\ag^i_j\leftarrow \p_i^{z_i-j}$, $a^i_j\leftarrow (y-r_i)^j$.
\STATE For $1\leq j\leq l-z_i$: $\ag^i_j\leftarrow \OK$,  $a^i_j\leftarrow y^j(y-r_i)^{z_i}$.
\STATE Let $\left(A_i,(\ag^i_j)_{j\leq l+1}\right)$ be the pseudo matrix representing $J_i^{z_i}$.
\STATE Compute $\g(J_i^{z_i})$ with Algorithm~\ref{alg:det_ideal} used with the bound $L$.
\ENDFOR
\STATE Compute a pseudo-basis $[(c_i),(\cg_i)]_{i\leq l+1}$ of $M=\cap_i J_i^{z_i}$ modulo $\g = \prod_i\g(J_i^{z_i})$ with algorithm~\ref{alg:int_OK_mod}.
\STATE Deduce a pseudo basis $[(d_i),(\dg_i)]_{i\leq l+1}$ of the module $M'$ given by
$$(v_0, v_1,\cdots,v_l)\in M\Longleftrightarrow (v_0, v_1\cdot B,\cdots,v_l\cdot(B)^l)\in M'.$$
\STATE Let $[(b_i),(\bg_i)]_{i\leq l+1}$ be a short peudo-basis of $M'$ obtained with the reduction algorithm of~\cite{stehle_fieker_LLL}.
\STATE Let $x_1,x_2$ be a short basis of $\bg_1$ obtained with~\cite[Th. 3]{stehle_fieker_LLL}.
\RETURN $c\in M$ corresponding to $x_1b_1\in M'$.
\end{algorithmic}
\end{algorithm}

\begin{proposition}
Algorithm~\ref{alg:comp_c} is correct and runs in polynomial time in $\log(N)$, $l$, $d$, and $\log|\Delta|$.
\end{proposition}

\begin{proof}
The loop between Step 1 and Step 8 of Algorithm~\ref{alg:comp_c} consists of computing a pseudo-basis for $J_i^{z_i}$ along with its determinantal ideal. These steps are polynomial in $K$, $l$, $d$ and $\log|\Delta|$. All we need to prove is that $L$ is indeed an upper bound on $\max_{k,g,\sigma}|\sigma(\left.A_i\right._{k,g})|$ where  $\sigma:K\rightarrow\C$ runs over the $d$ complex embeddings of $K$. Every $r_k$ can be written $r_k = \sum_{g\leq d}b^{(k)}_g\alpha_g$ where $(\alpha_g)_{g\leq d}$ is an integral basis of $\OK$. In addition, according to~\cite[Lem. 1]{stehle_fieker_LLL}, we may assume that $\|\alpha_g\|\leq \sqrt{d}2^{d^2/2}\sqrt{|\Delta|}$. Trivially, we see that our canonical choice for a representative of a class modulo $\p_k$ satisfies $|b^{(k)}_g|\leq \Nm(\p_k)$. We thus have
$$\forall \sigma,k, \ |\sigma(r_k)|\leq \|r_k\| \leq \Nm(\p_k)\sqrt{d}2^{d^2/2}\sqrt{|\Delta|}\leq N\sqrt{d}2^{d^2/2}\sqrt{|\Delta|}.$$
The coefficients of $A$ are given by those of polynomials of the form $(y-r_k)^g$ where $g\leq l$. They are bounded by
$$\max_{\sigma,k,g} |\sigma(\left.A_i\right._{k,g})|\leq \binom{2l}{l}(\max_{\sigma,k}|\sigma{r_k}|)^l\leq 2^{ld^2/2}\binom{2l}{l}N^l|\Delta|^{l/2}.$$
Givem the bounds on $\|\det(A_i)\|$, we clearly see that $\g = \prod\g(J_i^{z_i})$ has bit size polynomial in $\log(N)$, $l$, $d$ and $\log|\Delta|$, which implies that step 9 is polynomial in all these values.

By assumption, we know the existence of $e\in\prod_i J_i^{z_i}$ of degree at most $l$ satisfying~\eqref{eq:cond_norm} for $F$. We even argued in the proof of Lemma~\ref{lem:nb_pol} that we could assume 
$$\forall j\leq l, \ \|e_j\|\leq \frac{F}{(l+1)B^j}.$$
The size of the vector $e'$ corresponding to $e$ in the module $M'$ defined in Step~10 satisfies $\|e'\|\leq F/\sqrt{l+1}$, and so does the first minima $\lambda_1(M')$, that is $\lambda_1(M')\leq \|c'\| \leq  F/\sqrt{l+1}$. Note that we use $\|e\| = \sqrt{\sum_i \|e\|^2}$ to define the size of an element of an $\OK$-module. From~\cite[Th. 3]{stehle_fieker_LLL}, we know that $\Nm(\bg_1)\in[2^{-O(d^2)}, 1]$ and that 
\begin{align*}
\|x_1\| & \leq 4\cdot 2^{4d}|\Delta|^{4/d}\left(\max_{i\leq d}\|\alpha_i\|\right)^4\Nm(\bg_1)^{4/d} \\
&\leq 2^{2(1 + d(2 + d))}d^2|\Delta|^{2\left(1 + \frac{2}{d}\right)}.
\end{align*}
In addition, $\|b_1\|$ can be bounded by using~\cite[Cor. 3]{stehle_fieker_LLL}
\begin{align*}
\|b_1\| &\leq 2^{\frac{d(l+1)}{2}}\sqrt{l+1} 2^{\frac{3d}{2}}|\Delta|^{\frac{3}{2d}}\left(\max_{i\leq d}\|\alpha_i\|\right)^2\lambda_1(M')\\
&\leq 2^{d\left(\frac{l+1}{2} + \frac{3}{2} + d\right)}\sqrt{l+1}d|\Delta|^{\frac{3}{2d}}\lambda_1(M').
\end{align*}
We thus have that 
$$\|x_1b_1\|\leq \left(2^{2 + d\left(\frac{l+12}{2} + 3d\right)} d^3 |\Delta|^{2 + \frac{11}{2d}}\right)F,$$
and therefore, for every $m\in\OK$ such that $\|m\|\leq B$, the polynomial $c\in M$ corresponding to $x_1b_1\in M'$ satisfies
$$\|c(m)\|\leq \sqrt{l+1}\|x_1b_1\|\leq \sqrt{l+1}\|x_1\|\|b_1\|\leq  2^{\frac{dl}{2}}\sqrt{l+1}\left(2^{2 + d\left(6 + 3d\right)} d^3|\Delta|^{2 + \frac{11}{2d}}\right) F.$$
\end{proof}
\section{Good weight settings}\label{sec:weight}

To derive our main result, we need to consider weights $z_i > 0$ in $\R$ rather than $\Z$. Let 
$$\bdd := \frac{d^{3-\frac{d}{2}}2^{3\left(1 + d(2 + d)\right)}|\Delta|^{2 + \frac{11}{2d}}}{\left.\add\right.^{\frac{1}{d}}},$$
then by combining~\eqref{eq:cond_weight}, \eqref{eq:cond_F} and Algorithm~\ref{alg:comp_c}, we know that given $(r_1,\cdots,r_n)\in\prod_{i\leq n}\OK/\p_i$, $l>0$, $B = \prod_{i\leq k}\Nm(\p_i)$ and integer weights $z_i > 0$, Algorithm~\ref{alg:comp_c} returns a polynomial $c$ of degree at most $l$ such that all $m\in\OK$ satisfying $\|m\|\leq B$ and
\begin{align}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) \geq &\frac{l}{2}\log(2^{d^2}B^d) + \frac{3d}{2}\log(l+1) \nonumber \\
& + \frac{1}{l+1}\sum_{i\leq n}\binom{z_i+1}{2}\log\Nm(\p_i) + \log\bdd, \label{eq:dec_cond_fin}
\end{align}
(where $a_i = 1$ if $m\bmod \p_i = r_i$, 0 otherwise) are roots of $c$. In the following, we no longer assume the $z_i$ to be integers. However, we will use our previous results with the integer weights $z^*_i := \lceil Az_i\rceil$ for a sufficently large integer $A$ to be determined.

\begin{proposition}\label{prop:dec_final}
Let $\varepsilon > 0$, non-negative reals $z_i$, $B = \prod_{i\leq k}\Nm(\p_i)$, and an encoded message $(r_1,\cdots,r_n)\in\prod_i\OK/\p_i$, then our algorithm finds all the $m\in\OK$ such that $\|m\|\leq B$ and 
$$\sum_{i\leq n}a_iz_i\log\Nm(\p_i)\geq \sqrt{\log(2^{d^2}B^d)\left(\sum_{i\leq n}z^2_i\log\Nm(\p_i) + \varepsilon z^2_{max}\right)},$$
where $a_i = 1$ if $m\bmod \p_i = r_i$, 0 otherwise.
\end{proposition}

\begin{proof}
Note that we can assume without loss of generality that $z_{max} = 1$. Let $z^*_i = \lceil Az_i\rceil$ for a sufficently large integer $A$, which thus satisfies $Az_i\leq z^*_i < Az_i + 1$. The decoding condition~\eqref{eq:dec_cond_fin} is met whenever 
\begin{align}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) \geq &\frac{l}{2A}\log(2^{d^2}B^d) + \frac{3d}{2A}\log(l+1) \nonumber \\
& + \frac{A}{2(l+1)}\sum_{i\leq n}\left(z^2_i + \frac{3}{A}z_i + \frac{2}{A^2}\right)\log\Nm(\p_i) + \frac{1}{A}\log\bdd. \label{eq:dec_cond_A}
\end{align}

Let $Z_i := z^2_i + \frac{3}{A}z_i + \frac{2}{A^2}$ for $i\leq n$ and
$$l := \left\lceil A\sqrt{\frac{\sum_{i\leq n}Z_i \log\Nm(\p_i)}{\log(2^{d^2}B^d)}}\right\rceil - 1.$$
We assume that $A\geq \log(2^{d^2}B^d)$, which ensures that $l > 0$. For this choice of $l$, condition~\eqref{eq:dec_cond_A} is satisfied whenever 
\begin{align}
\sum_{i\leq n} a_iz_i\log\Nm(\p_i) \geq & \frac{3d}{2A}\log\left(A\sqrt{\frac{\sum_{i\leq n}Z_i \log\Nm(\p_i)}{\log(2^{d^2}B^d)}}+1\right) \nonumber \\
& + \sqrt{\log(2^{d^2}B^d)\left(\sum_{i\leq n}Z_i\log\Nm(\p_i)\right)} + \frac{1}{A}\log\bdd. \label{eq:dec_cond_l}
\end{align}
Assume that $A \geq \frac{10\log N}{\varepsilon}$ and $A\geq \frac{\log\bdd}{\log N}$, then for $N$ large enough, the right side of~\eqref{eq:dec_cond_l} is at most
\begin{align*}
&O\left(\frac{\log\log N}{\log N}\right) +\sqrt{\log(2^{d^2}B^d) \left(\sum_{i\leq n}z^2_i\log\Nm(\p_i) + \frac{\varepsilon}{2}\right)}\\
&\leq \sqrt{\log(2^{d^2}B^d) \left(\sum_{i\leq n}z^2_i\log\Nm(\p_i) + \varepsilon\right)}
\end{align*}
The degree $l$ of our decoding polynomial $c$ is therefore polynomial in $\log N$, $\frac{1}{\varepsilon}$, $d$ and $\log|\Delta|$. By~\cite[2.3]{ayad}, we know that the complexity to find the roots of $c$ is polynomial in $d$, $l$ and in the logarithm of the height of $c$, which we already proved to be polynomial in the desired values.

\end{proof}

\begin{corollary}
Let $\varepsilon > 0$, $k < n$ and prime ideals $\p_1,\cdots\p_n$ satisfying $\Nm(\p_i) < \Nm(\p_{i+1})$ and $\log\Nm(\p_{k+1}) \geq \max(2dk\log\Nm(\p_k) , 2d^2)$, then with the previous notations, our algorithm finds a list of all codewords which agree with a received word in $t$ places provided $t\geq\sqrt{k(n+\varepsilon)}$.
\end{corollary}

\begin{proof}
The proof is similar to the one of~\cite[Th. 7.14]{guruswami_phd}. The main difference is that we define $\delta := k - \frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})}$ which satisfies $\delta \geq 0$ since by assumption $\log\Nm(\p_{k+1}) \geq \max(2dk\log\Nm(\p_k) , 2d^2)$. We apply Proposition~\ref{prop:dec_final} with $z_i = 1/\log \Nm(\p_i)$ for $i\geq k+1$, $z_i = 1/\log \Nm(\p_{k+1})$ for $i\leq k$, and $\varepsilon' = \varepsilon /\log\Nm(\p_{k+1})$. It allows us to retrieve the codewords whose number of agreements $t$ is at least 
\begin{align*}
&\sqrt{\frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})}\left( \frac{\log(B)}{\log\Nm(\p_{k+1})} + \sum^n_{i =k+1}\frac{\Nm(\p_{k+1})}{\log\Nm(\p_i)} + \varepsilon'\right)}\\
&\leq \delta + \sqrt{\frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})}\left( \frac{\log(2^{d^2}B^d)}{\log\Nm(\p_{k+1})} + \sum^n_{i =k+1}\frac{\Nm(\p_{k+1})}{\log\Nm(\p_i)} + \varepsilon \right)}.
\end{align*}
This condition is met whenever $t\geq \delta + \sqrt{(k-\delta)(n-\delta+\varepsilon)}$. From the Cauchy-Schwartz inequality, we notice that 
$$\sqrt{k(n+\varepsilon)} \geq \sqrt{(k-\delta)(n-\delta+\varepsilon)},$$
which proves that our decoding algorithm works when $t\geq\sqrt{k(n+\varepsilon)}$.
\end{proof}

\section{Conclusion}

We derived an analogue of the CRT list decoding algorithm for codes based on number fields. Our method allows to reach the Johnson bound. We followed the approach of~\cite[Ch. 7]{guruswami_phd} that provides a general frameworks for list decoding of algebraic codes, along with its application to CRT codes. The modifications to make this strategy efficient in the context of number fields are substantial. We needed to refer to the theory of modules over a Dedekind domain, and carefully analyse the process of intersecting them, as well as finding a short basis. Our algorithm is polynomial in $d$, $\log(N)$ and in $\log|\Delta|$. The only regret we can have is that we need to assume $\log\Nm(\p_{k+1}) \geq \max(2dk\log\Nm(\p_k) , 2d^2)$, which is the only difference with the result of~\cite[Ch. 7]{guruswami_phd} on CRT codes.

We could not conclude on whether the numer field codes can allow better decoding settings than CRT codes. So far, we have shown that they were effective and at least as good as CRT codes. Other types of decoding could be tried. In addition, more fundamental questions could be raised, for example on the performances of the dual code of a number field code. 

\bibliography{paper}

\end{document}
